package com.代码随想录.回溯;

import java.util.*;

/**
 * 回溯专题 速刷
 * 回溯问题 ：
 * 1.组合
 * 2.分割
 * 3.子集
 * 4.排列
 * 5.棋盘问题
 * 5.其他
 *
 * @author： leon
 * @description：
 * @date： 2022/9/24
 * @version: 1.0
 */
public class Solution {
    /**
     * 1.组合问题
     */
    /* =================================================================*/

    /**
     * 77. 组合问题
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        int start = 1;
        backtracking(n, k, start, tmp, ans);
        return ans;
    }

    private void backtracking(int n, int k, int start, List<Integer> tmp, List<List<Integer>> ans) {
        if (tmp.size() == k) {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        /** 无需遍历到 n ，可以提前剪枝 */
        for (int i = start; i <= n-k+tmp.size()+1; i++) {
            tmp.add(i);
            backtracking(n, k, i+1, tmp, ans);
            tmp.remove(tmp.size()-1);
        }
    }


    /**
     * 216. 组合总和 III
     * 只使用数字1到9
     * 每个数字 最多使用一次
     * @param k k个数
     * @param n 和为n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k>9){
            // 只能是9个数字内
            return null;
        }
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        // 用作记录元素和
        int total = 0;
        int start = 1;
        backtracking1(n, k, start, tmp, ans,total);
        return ans;

    }

    private void backtracking1(int n, int k, int start, List<Integer> tmp, List<List<Integer>> ans,int total) {
        if (tmp.size() == k&&total == n){
            ans.add(new ArrayList<>(tmp));
            return;
        }
        // 剪枝  i<=n-total
        for (int i = start; i <= 9 && i<=n-total; i++) {
            tmp.add(i);
            total+=i;
            backtracking1(n, k, i+1, tmp, ans,total);
            tmp.remove(tmp.size()-1);
            total-=i;
        }

    }

    /**
     * 17. 电话号码的字母组合
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        if(digits==null|| digits.length()==0){
            return new ArrayList<>();
        }


        int[] nums = Arrays.stream(digits.split("")).mapToInt(Integer::parseInt).toArray();
        String[] map = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        StringBuilder sb = new StringBuilder();
        List<String> ans = new ArrayList<>();
        backtracking(map,nums,sb,ans,0);
        return ans;
    }

    public void backtracking(String[] map,int[] nums,StringBuilder sb,List<String> ans,int idx){
        // 结束条件
        if (sb.length()== nums.length){
            ans.add(sb.toString());
            return;
        }
        String tmp = map[nums[idx]];
        for (int i = 0; i < tmp.length(); i++) {
            sb.append(tmp.charAt(i));
            backtracking(map,nums,sb,ans,idx+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    /**
     * 39. 组合总和
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }

    /**
     * 40. 组合总和 II,解集不能包含重复的组合,数组中每个位置的数字在每个组合中只能使用一次(比如 1，1，2),那么前面的1只能使用一次，后面的1也可以一次。 而且要求 不能出现同样的组合
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res= new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking1(res,path,candidates,target,0,0);
        return res;

    }

    public void backtracking1(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {

        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = idx; i < candidates.length&&sum+candidates[i]<=target; i++) {
            // 保证 当前层 的当前 值，以前没有出现过，通过这样做的去重的操作（首先要排序）
            if ((i==idx||candidates[i]!=candidates[i-1])){
                path.add(candidates[i]);
                sum+=candidates[i];
                backtracking1(res,path,candidates,target,sum,i+1);
                path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
                sum-=candidates[i];
            }
        }
    }

    /**
     * 131. 分割回文串 ；
     * 动态规划 + 递归回溯
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        // 先用动态规划 计算任意区间 是否是 回文串。
        int n = s.length();
        boolean[][] isPd = new boolean[n][n];

        for (int i = 0; i < 2 * n - 1; i++) {
            int l = i/2,r=i/2+i%2;
            while (l>=0&&r<n&&s.charAt(l)==s.charAt(r)){
                isPd[l][r] = true;
                l--;
                r++;
            }
        }


        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();

        backtracking(ans,path,0,s,isPd);
        return ans;
    }

    public void backtracking(List<List<String>> ans,List<String> path,int startIdx,String s,boolean[][] map){
        if (startIdx == s.length()){
            ans.add(new ArrayList<>(path));
        }
        for (int i = startIdx; i < s.length(); i++) {
            if (map[startIdx][i]){
                path.add(s.substring(startIdx,i+1));
                backtracking(ans,path,i+1,s,map);
                path.remove(path.size()-1);
            }
        }

    }

    public static void main(String[] args) {
        final Solution solution = new Solution();
        solution.partition("abbab");
    }

}
